Suchalgorithmen

Suchalgorithmen,

 

Verfahren (Algorithmen), in einem vorgegebenen Datenbestand ein oder alle Objekte zu ermitteln, die eine bestimmte Bedingung, das Suchkriterium, erfüllen. Folgende Suchalgorithmen sind gebräuchlich:

 

sequenzielle Suche: Nacheinander werden die Objekte einer Liste angesehen, bis ein Objekt gefunden wird, welches das Suchkriterium erfüllt. Anschließend wird in gleicher Weise fortgesetzt, um weitere Objekte zu finden. Dieses Verfahren ist einfach, aber zeitaufwendig.

 

binäre Suche: In einer auf- oder absteigend sortierten Liste wird fortgesetzt der Bereich halbiert, in dem sich ein gesuchtes Objekt noch befinden kann. Dieser Algorithmus arbeitet schnell und effizient, da er mit wenigen Schritten zum Ziel kommt: Eine Verdoppelung der Objektzahl erfordert im Mittel lediglich eine zusätzliche Bereichshalbierung.

 

Suche auf einem binären Baum: Alle Objekte werden aus einer nach dem Suchkriterium sortierten und aufsteigend nummerierten Liste in einen binären Baum so einsortiert, dass die Einträge des linken Teilbaums kleinere Listennummern als der übergeordnete Knoteneintrag aufweisen und entsprechend die Einträge des rechten Teilbaums nach dem Knoteneintrag größere, und dies für alle Knoten. Die Suche beginnt oben an der Baumwurzel. Erfüllt der Wurzeleintrag das Suchkriterium, ist die Suche sofort erfolgreich gewesen. Sucht man nach einer kleineren Nummer als der des Wurzeleintrags, verzweigt man im Baum nach links in die nächste Knotenebene, andernfalls nach rechts. Anschließend setzt man an dem erreichten Knoten in gleicher Weise fort. Die Suche endet nach spätestens so vielen Abfragen, wie Verzweigungen möglich sind. Damit ist die Suche auf einem binären Baum ebenfalls ein effizienter Suchalgorithmus.

 

Bei der Suche auf nicht binären, aber geordneten Baumstrukturen wie z. B. dem B-Baum (Baum) verwendet man ähnliche Suchalgorithmen, zusätzlich werden alle Nachfolger eines Knotens wie bei einer geordneten Liste durchsucht. Einen Baum, der vorwiegend für effizientes Suchen eingerichtet ist, nennt man Suchbaum. Von Bedeutung ist außerdem das Hash-Verfahren.

 

Generell sind die Suchalgorithmen, die auf einer vorherigen Sortierung und Vorstrukturierung der Daten beruhen, wesentlich effizienter als die einfache sequenzielle Suche. Zu berücksichtigen ist allerdings der Aufwand für die Sortierung. Wenn etwa häufig neue Daten in die Datenliste aufgenommen werden und die Liste insgesamt nur wenige Einträge aufweist, fällt die Sortierung ins Gewicht.